Systems for optimistic replication of resources are becoming increasingly important to ensure availability and fault tolerance in large networks. Corporate networks that replicate objects containing domain credentials and policies are one example where availability, scalability, consistency, and reliability are critical. These requirements do not necessarily interact in a cooperative manner.
One situation where the requirements for performance, scalability, and consistency collide is in propagating resource deletion information. The deletion of a resource on one machine is communicated to other machines by sending a notification referred to as a tombstone notification, or simply a tombstone. These tombstones are propagated through the network to ensure that the machines that participate in replication are notified about the deletion of a resource. As more and more tombstones accumulate due to resources being created and deleted, deleting the tombstones themselves becomes essential to limiting the amount of meta-data required for replication. However, tombstone deletion (sometimes called garbage collecting the tombstone) has not been solved in a satisfactory way in previous art.